package hot_100;

import java.util.LinkedList;
import java.util.List;

public class N皇后 {
    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(4);
        for (List<String> list : lists) {
            System.out.println(list);
        }
    }

    static int h;
    static int[] visxx;
    static int[] visyy;
    static int[] visx;
    static int[] visy;
    static List<List<String>> ans = new LinkedList<>();
    static List<String> t = new LinkedList<>();

    public static List<List<String>> solveNQueens(int n) {
        h = n;
        visx = new int[n + 1];
        visy = new int[n + 1];
        visxx = new int[2 * n + 1];
        visyy = new int[2 * n + 1];
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            t.add(sb.toString());
        }
        Dfs(1, h);
        return ans;
    }

    public static void Dfs(int x, int cnt) {
        if (x > h) {
            if (cnt == 0)
                ans.add(new LinkedList<>(t));
            return;
        }
        for (int y = 1; y <= h; y++) {
            if (check(x, y)) {
                update(x, y, 1);
                Dfs(x + 1, cnt - 1);
                update(x, y, 0);
            }
        }
    }

    public static boolean check(int x, int y) {
        return visx[x] != 1 && visy[y] != 1 && visxx[x + y] != 1 && visyy[x - y + h] != 1;
    }

    public static void update(int x, int y, int is) {
        visx[x] = visy[y] = visxx[x + y] = visyy[x - y + h] = is;
        char[] ch = t.get(x - 1).toCharArray();
        if (is == 1) {
            ch[y - 1] = 'Q';
        } else {
            ch[y - 1] = '.';
        }
        t.set(x - 1, new String(ch));
    }
}
